/**************************************************************************
* DS_WILDCARD.CPP                                              12.03.2007 *
*                                                                         *
* .                                                                       *
**************************************************************************/

#include "stdafx.h"

namespace ds {

struct WILDCARD_TOKENIZER {
   WILDCARD::STRING_TABLE & direct;
   WILDCARD::STRING_TABLE & revert;
   WILDCARD::STRING_TABLE * curTable;
   WILDCARD::STRING_ARRAY * curLine;

   WILDCARD_TOKENIZER(WILDCARD::STRING_TABLE & direct, WILDCARD::STRING_TABLE & revert)
      : direct(direct), revert(revert)
   {
      curTable = &direct;
      curTable->PushBack(WILDCARD::STRING_ARRAY(AP_CL));
      curLine  = &direct.Back();
   }

   ds::TOKENIZE_RESULT ProcessToken(const char * token, int length)
   {
      if (length != 0) {
         curLine->PushBack(token);
      }

      return ds::TOKENIZE_CONTINUE;
   }

   ds::TOKENIZE_RESULT ProcessDelim(char delim)
   {
      switch (delim) {
      case '*':
         curLine->PushBack(dsSTRING()); // empty string means 'asterics'
         break;
      case '|':
         curTable->PushBack(WILDCARD::STRING_ARRAY(AP_CL));
         curLine = &curTable->Back();
         break;
      case '~':
         curTable = (curTable == &direct) ? &revert : &direct;
         curTable->PushBack(WILDCARD::STRING_ARRAY(AP_CL));
         curLine = &curTable->Back();
         break;
      }

      return ds::TOKENIZE_CONTINUE;
   }
};

/**************************************************************************
* WILDCARD::Parse()                                                       *
*                                                                         *
**************************************************************************/
void WILDCARD::Init(const dsSTRING & filter_, bool caseSensitive /*= true*/)
{
   Term();

   this->caseSensitive = caseSensitive;
   dsSTRING filter = !caseSensitive ? filter_ : filter_.Lower();

   WILDCARD_TOKENIZER tokenizer(direct, revert);
   ds::Tokenize(filter, "*|~", tokenizer);

   // "~xyz" should be same as "*~xyz"
   if (direct.Length() == 1 && direct[0].IsEmpty()) {
      direct += STRING_ARRAY(AP_CL);
      direct[0] += "";
   }
}

/**************************************************************************
* WILDCARD::Term()                                                        *
*                                                                         *
**************************************************************************/
void WILDCARD::Term(void)
{
   direct.Clear();
   revert.Clear();
}

/**************************************************************************
* FILTER::Match()                                                         *
*                                                                         *
**************************************************************************/
bool WILDCARD::Match(const dsSTRING & text_) const
{
   dsSTRING text = !caseSensitive ? text_ : text_.Lower();

   // check positive masks
   bool res = false;
   for (int i=0; i<direct.Length(); ++i) {
      if (Match(text, direct[i])) {
         res = true;
         break;
      }
   }

   if (!res) {
      return false;
   }

   // check negative masks
   for (int i=0; i<revert.Length(); ++i) {
      if (Match(text, revert[i])) {
         return false;
      }
   }
   return true;
}

/**************************************************************************
* FILTER::Match()                                                         *
*                                                                         *
**************************************************************************/
bool WILDCARD::Match(const dsSTRING & text, const STRING_ARRAY & mask) const
{
   typedef unsigned char uchar;

   // if mask is empty - everything is false but empty string
   if (mask.IsEmpty()) {
      return text.IsEmpty();
   }

   // if text is empty check that mask has only asterisks
   if (text.IsEmpty()) {
      for (int i=0; i<mask.Length(); ++i) {
         if (!mask[i].IsEmpty()) {
            return false;
         }
      }
      return true;
   }

   // prepare match line
   dsVECTOR<int> matchLine;
   for (int i=0; i<mask.Length(); ++i) {
      if (mask[i].IsEmpty()) {
         matchLine.PushBack(-1); // -1 means asterisk
         continue;
      }

      for (int j=0; j<mask[i].Length(); ++j) {
         matchLine.PushBack((uchar)mask[i][j]);
      }
   }

   // fill table [text]x[mask] by 'false'
   dsVECTOR<bool> line0(matchLine.Length(), false);
   dsVECTOR<bool> line1 = line0;

   // initialize
   int index = 0;
   for (int i=0; i<matchLine.Length(); ++i) {
      if (matchLine[i] == -1) {
         if (i == 0 || line0[i-1]) {
            line0[i] = true;
         }
      }
      if (matchLine[i] == (uchar)text[index]) {
         if (i == 0 || i > 0 && matchLine[i-1] == -1 && line0[i-1]) {
            line0[i] = true;
         }
      }
   }

   // make steps
   for (index = 1; index < text.Length(); ++index) {
      for (int i=0; i<matchLine.Length(); ++i) {
         if (matchLine[i] == -1) {
            if (i == 0 || line0[i-1] || line0[i] || line1[i-1]) {
               line1[i] = true;
            }
         }
         if (matchLine[i] == (uchar)text[index]) {
            if (i > 0 && line0[i-1] || i > 0 && matchLine[i-1] == -1 && line1[i-1]) {
               line1[i] = true;
            }
         }
      }
      line0 = line1;
      line1.Clear();
      line1.Resize(matchLine.Length(), false);
   }

   return line0.Back();
}

/**************************************************************************
* WILDCARD::WILDCARD()                                                    *
*                                                                         *
**************************************************************************/
WILDCARD::WILDCARD(void)
   : direct(AP_CL), revert(AP_CL)
   , caseSensitive(true)
{
   // by default match everything
   direct.PushBack(STRING_ARRAY(AP_CL));
   direct[0].PushBack(dsSTRING());
}

/******************************************************************************/
/* ds::SIMPLE_WILDCARD::Init
/*
/******************************************************************************/
void SIMPLE_WILDCARD::Init(const char * rule)
{
   prefix = middle = suffix = dsSTRING();

   const char * cur = rule;
   char buf[256];

   // prefix
   if (*cur != '*') {
      const char * end = strchr(cur, '*');
      if (end == NULL) {
         //ASSERT_ALOOF_CODE();
         prefix = rule;
         return ;
      }

      int length = end - cur;
      STRONG_ASSERT2(length < 256, end - cur, rule);
      memcpy(buf, cur, length);
      buf[length] = 0;

      prefix      = buf;
      cur         = end;
   }

   // middle part
   STRONG_ASSERT(*cur == '*');
   ++cur;

   if (*cur == 0) {
      // prefix*
      return ;
   }

   const char * end = strchr(cur, '*');
   if (end == NULL) {
      // prefix*suffix
      suffix = cur;
      return ;
   }

   // prefix*middle*[suffix]
   int length = end - cur;
   STRONG_ASSERT2(length < 256, end - cur, rule);
   memcpy(buf, cur, length);
   buf[length] = 0;
   
   middle = buf;
   cur    = end;

   ++cur;
   if (*cur == 0) {
      // prefix*middle*
      return ;
   }

   suffix = cur;
   STRONG_ASSERT2(strchr(cur, '*') == NULL, cur, rule);
}

/******************************************************************************/
/* ds::SIMPLE_WILDCARD::Match
/*
/******************************************************************************/
bool SIMPLE_WILDCARD::Match(const char * text) const
{
   // TODO: Support "Ignore Case"

   int length     = strlen(text);
   int minLength  = prefix.Length() + middle.Length() + suffix.Length();

   if (length < minLength) {
      return false;
   }

   if (!prefix.IsEmpty() && !startswith(text, prefix)) {
      return false;
   }
   if (!suffix.IsEmpty() && !equals(text + length - suffix.Length(), suffix)) {
      return false;
   }

   // no middle, return true
   if (middle.IsEmpty()) {
      return true;
   }

   const char * rest = text + prefix.Length();

   const char * pos = strstr(rest, middle.CStr());
   if (pos == NULL) {
      return false;
   }

   if (pos - rest > length - minLength) {
      return false;
   }

   return true;
}

} // namespace ds

//
// End-of-file DS_WILDCARD.CPP
//
